package swordoffer.offer03;

public class Solution3_2 {
    public static void main(String[] args) {
        int[] nums = new int[1001];
        for (int i = 0;i<nums.length;i++){
            nums[i] = (int)((Math.random()*1000)+1);
        }
        int duplication = getDuplication(nums);
        System.out.println("duplication = " + duplication);
    }
    public static int getDuplication(int[] nums){
        if (nums == null || nums.length <= 0 ){
            return -1;
        }
        int N = nums.length;
        int start = 1;
        int end = N - 1;
        while (end >= start){
            int mid = start + (end - start) / 2;
            int count = countRange(nums,start,mid);
            if (end == start){
                if (count > 1){
                    return start;
                }else {
                    break;
                }
            }
            //如果count > 该区间元素的数量，说明存在重复元素
            if (count > (mid - start+1)){
                end = mid;
            }else {
                start = mid + 1;
            }
        }

        return -1;
    }

    private static int countRange(int[] nums, int start, int mid) {
        int count = 0;
        for (int i = 0 ; i < nums.length; i++){
            if (nums[i] >= start && nums[i] <= mid){
                count++;
            }
        }
        return count;
    }
}
